#include "fabric.h"
#include "include.h"


//-------------------------------------------------------------------------------------------
Fabric::Fabric(float width, int resolution, QList<Piece> pieces, bool rotate90, bool rotate180, bool rotate270, bool vertical_mirror, bool horizontal_mirror, int sort_method, int alghoritm)
{
	this->width = width;
	this->pieces = pieces;
	this->resolution = resolution;
	this->height = 99999999;
	this->used_alghoritm = alghoritm;
	this->sort_method = sort_method;
	this->rotations[0] = true;
	this->rotations[1] = rotate90;
	this->rotations[2] = rotate180;
	this->rotations[3] = rotate270;
	this->vertical_mirror = vertical_mirror;
	this->horizontal_mirror = horizontal_mirror;
}

//-------------------------------------------------------------------------------------------
Fabric::Fabric()
{	
	this->width = 0;
	this->resolution = 0;
}

//-------------------------------------------------------------------------------------------
QList<Piece> Fabric::getSolution()
{
	return this->solution;
}

//-------------------------------------------------------------------------------------------
void Fabric::setWidth(float width)
{
	this->width = width;
}

//-------------------------------------------------------------------------------------------
float Fabric::getWidth()
{
	return this->width;
}

//-------------------------------------------------------------------------------------------
float Fabric::getHeight()
{
	return this->height;
}

//-------------------------------------------------------------------------------------------
float Fabric::piecesArea()
{
	float pieces_area = 0.0;
	Piece piece;
	for (int i = 0; i < this->pieces.size(); i++){
		piece = this->pieces.at(i);
		pieces_area += piece.area();
	}
	return pieces_area;
}
 
//-------------------------------------------------------------------------------------------
void Fabric::resolveCut()
{
	float aprox_height = qMax(500, qRound(this->piecesArea() / this->width * 3));
	
	this->fabric_mask = Mask(this->width, aprox_height, this->resolution);
	
	switch (this->sort_method){
	case 0: this->createMasks(); break;
	case 1:{
		this->pieces = this->sortByArea(false);
		this->createMasks();
	} break;
	case 2:{
		this->pieces = this->sortByArea(true);
		this->createMasks();
	} break;
	case 3:{
		this->pieces = this->sortByWaste(false);
	} break;
	case 4:{
		this->pieces = this->sortByWaste(true);
	} break;
	}
	
	switch (this->used_alghoritm){
	case BackTracking1: {
		int partial_height = 0;
		this->height = 99999999;
		QList<Piece> partial_solution;
		QList<int> visited_pieces;
		Mask partial_mask = this->fabric_mask;
		this->heurisResult();
		this->backResult(this->pieces, this->masks, visited_pieces, partial_height, this->height, partial_solution, this->solution, partial_mask, this->fabric_mask);
	} break;
	case BackTracking2:{
		int depth = qMin(6, this->pieces.size());
		this->depthBackResult(depth);
	} break;
	case Heuristic1: this->heurisResult(); break;
	case Heuristic2: this->optimizedHeurisResult(); break;
	}
}

//-------------------------------------------------------------------------------------------
void Fabric::draw(QPainter *painter, bool showGrid, bool showPieces, bool distinguishCells)
{
	if (showPieces)
		for (int i = 0; i < this->solution.size(); i++){
			Piece piece = this->solution.at(i);
			piece.draw(painter, POLYGON);
		}
	if (showGrid) this->fabric_mask.draw(painter, distinguishCells);
}

//--------------------------------------------------------------------------------------------
QList<Piece> Fabric::sortByArea(bool descendent)
{
	QList<Piece> sort_list;
	for (int i = 0; i < this->pieces.size(); i++){
		bool inserted = false;
		Piece piece = this->pieces.at(i);
		for (int j = 0; j < sort_list.size() && !inserted; j++){
			Piece current_piece = sort_list.at(j);
			if (descendent){
				if (piece.area() > current_piece.area()){
					inserted = true;
					sort_list.insert(j, piece);
				}
			}else{
				if (piece.area() < current_piece.area()){
					inserted = true;
					sort_list.insert(j, piece);
				}
			}	
		}
		if (!inserted)
			sort_list.push_back(piece);	
	}
	return sort_list;
}

//---------------------------------------------------------------------------------------------
QList<Piece> Fabric::sortByWaste(bool descendent)
{
	QList<Piece> sort_list;
	for (int i = 0; i < this->pieces.size(); i++){
		bool inserted = false;
		Piece piece = this->pieces.at(i);
		Mask mask(piece, this->resolution);
		for (int j = 0; j < sort_list.size() && !inserted; j++){
			//Piece current_piece = sort_list.at(j);
			Mask current_mask = this->masks.at(j);
			if (descendent){
				if (mask.freePixels() > current_mask.freePixels()){
					inserted = true;
					sort_list.insert(j, piece);
					this->masks.insert(j, mask);
				}
			}else{
				if (mask.freePixels() < current_mask.freePixels()){
					inserted = true;
					sort_list.insert(j, piece);
					this->masks.insert(j, mask);
				}
			}	
		}
		if (!inserted){
			sort_list.push_back(piece);
			this->masks.push_back(mask);
		}
	}
	return sort_list;
}

//---------------------------------------------------------------------------------------------
void Fabric::createMasks()
{
	for (int i = 0; i < this->pieces.size(); i++)
		this->masks += Mask(this->pieces.at(i), this->resolution);
}

//---------------------------------------------------------------------------------------------
void Fabric::heurisResult()
{
	int solution_height = 0;
	for (int i = 0; i < this->masks.size(); i++){
		Mask mask = this->masks.at(i);
		Piece piece = this->pieces.at(i);
		int row, column, height;
		height = this->bestSelection(this->fabric_mask, mask, piece, row, column);
		this->fabric_mask.combine(mask, row, column);
		this->solution += piece;
		solution_height = (int) qMax(solution_height, height);
	}
	this->height = solution_height;
}

//---------------------------------------------------------------------------------------------
void Fabric::optimizedHeurisResult()
{
	int solution_height = 0;
	int residue = (int) fmod(this->masks.size(), 2);
	for (int i = 0; i < this->masks.size() - residue; i += 2){
		int row, column, height1, height2, partial_height1 = solution_height, partial_height2 = solution_height;
		Mask partial_mask1 = this->fabric_mask, partial_mask2 = this->fabric_mask;
		QList<Piece> partial_solution1 = this->solution, partial_solution2 = this->solution;
		Mask mask1 = this->masks.at(i);
		Piece piece1 = this->pieces.at(i);
		Mask mask2 = this->masks.at(i+1);
		Piece piece2 = this->pieces.at(i+1);
		
		height1 = this->bestSelection(partial_mask1, mask1, piece1, row, column);
		partial_height1 = (int) qMax(partial_height1, height1);
		partial_mask1.combine(mask1, row, column);
		partial_solution1 += piece1;
		height1 = this->bestSelection(partial_mask1, mask2, piece2, row, column);
		partial_height1 = (int) qMax(partial_height1, height1);
		partial_mask1.combine(mask2, row, column);
		partial_solution1 += piece2;
		
		height2 = this->bestSelection(partial_mask2, mask2, piece2, row, column);
		partial_height2 = (int) qMax(partial_height2, height2);
		partial_mask2.combine(mask2, row, column);
		partial_solution2 += piece2;
		height2 = this->bestSelection(partial_mask2, mask1, piece1, row, column);
		partial_height2 = (int) qMax(partial_height2, height2);
		partial_mask2.combine(mask1, row, column);
		partial_solution2 += piece1;
		
		if (height2 > height1){
			solution_height = partial_height1;
			this->fabric_mask = partial_mask1;
			this->solution = partial_solution1;
		}else{
			solution_height = partial_height2;
			this->fabric_mask = partial_mask2;
			this->solution = partial_solution2;
		}
	}
	if (residue == 1){
		int row, column, height;
		Mask mask = this->masks.last();
		Piece piece = this->pieces.last();
		height = this->bestSelection(this->fabric_mask, mask, piece, row, column);
		solution_height = qMax(height, solution_height);
		this->fabric_mask.combine(mask, row, column);
		this->solution += piece;
	}
		
	this->height = solution_height;
}

//---------------------------------------------------------------------------------------------
void Fabric::backResult(QList<Piece> pieces, QList<Mask> masks, QList<int> &visited_pieces, int &partial_height, float &s_height, QList<Piece> &partial_solution, QList<Piece> &solution, Mask &partial_mask, Mask &fabric_mask)
{
	if (visited_pieces.size() != pieces.size()){
		int last_height = partial_height;
		Mask last_mask = partial_mask;
		for (int i = 0; (i < masks.size()) && (partial_height < s_height); i++)
			if (!visited_pieces.contains(i)){
				Mask mask = masks.at(i);
				Piece piece = pieces.at(i);
				int row, column, height;
				height = this->bestSelection(partial_mask, mask, piece, row, column);
				partial_mask.combine(mask, row, column);
				partial_solution += piece;
				partial_height = (int) qMax(height, partial_height);
				visited_pieces += i;
				this->backResult(pieces, masks, visited_pieces, partial_height, s_height, partial_solution, solution, partial_mask, fabric_mask);
				visited_pieces.pop_back();
				partial_solution.pop_back();
				partial_mask = last_mask;
				partial_height = last_height;
			}
	}else{
		if (partial_height < s_height){
			s_height = partial_height;
			solution = partial_solution;
			fabric_mask = partial_mask;
		}
	}
}

//---------------------------------------------------------------------------------------------
void Fabric::depthBackResult(int depth)
{
	QList<Piece> pieces = this->pieces;
	QList<Mask> masks = this->masks;
	QList<Piece> partial_solution;
	Mask partial_mask = this->fabric_mask;
	int partial_height = 0;
	
	while (!pieces.empty()){
		QList<Piece> current_pieces;
		QList<Mask> current_masks;
		QList<int> visited_pieces;
		
		for (int i = 0; i < depth && !pieces.empty(); i++){
			current_pieces += pieces.first();
			current_masks += masks.first();
			pieces.removeFirst();
			masks.removeFirst();
		}
		
		this->height = 99999999;
		
		this->backResult(current_pieces, current_masks, visited_pieces, partial_height, this->height, partial_solution, this->solution, partial_mask, this->fabric_mask);
		
		partial_height = (int) this->height;
		partial_solution = this->solution;
		partial_mask = this->fabric_mask;
	}
}

//---------------------------------------------------------------------------------------------
int Fabric::bestSelection(Mask fabric_mask, Mask &piece_mask, Piece &piece, int &row, int &column)
{
	Mask initial_mask = piece_mask;
	Piece initial_piece = piece;
	bool vm, hm;
	int partial_row, partial_column, rot; 
	int height = 999999, vertical_mirrors = 0, horizontal_mirrors = 0;
	if (this->vertical_mirror) vertical_mirrors = 1;
	if (this->horizontal_mirror) horizontal_mirrors = 1;
	
	for (int r = 0; r <= 4; r++){
		
		Mask partial_mask = initial_mask;
		Piece partial_piece = initial_piece;
		
		if (this->rotations[r] == true){
			if (r == 1){
				partial_mask.rotateMe();
				partial_piece.rotateMe(90);
			}
			if (r == 2){
				partial_mask.rotateMe();
				partial_mask.rotateMe();
				partial_piece.rotateMe(180);
			}
			if (r == 3){
				partial_mask.rotateMe();
				partial_mask.rotateMe();
				partial_mask.rotateMe();
				partial_piece.rotateMe(270);
			}
			
			rot = r;
						
			for (int v = 0; v <= vertical_mirrors; v++){
				Mask partial_mask2 = partial_mask;
				Piece partial_piece2 = partial_piece;
				vm = false;
				if (v == 1){
					partial_mask2.reflectMe(Vertical);
					partial_piece2.reflectMe(Vertical);
					vm = true;
				}
				for (int h = 0; h <= horizontal_mirrors; h++){
					Mask partial_mask3 = partial_mask2;
					Piece partial_piece3 = partial_piece2;
					hm = false;
					if (h == 1){
						partial_mask3.reflectMe(Horizontal);
						partial_piece3.reflectMe(Horizontal);
						hm = true;
					}
					this->bestPlace(fabric_mask, partial_mask3, partial_row, partial_column);
					if (height > partial_row * this->resolution + partial_mask3.height()){
						row = partial_row;
						column = partial_column;
						piece_mask = partial_mask3;
						piece = partial_piece3;
						this->placePiece(piece, piece_mask, rot, vm, hm, row, column);
						height = partial_row * this->resolution + partial_mask3.height();
					}
				}
			}
		}
	}
	return height;
}

//---------------------------------------------------------------------------------------------
bool Fabric::bestPlace(Mask fabric_mask, Mask piece_mask, int &row, int &column)
{
	for (int i = 0; i + piece_mask.countRows() - 1 < fabric_mask.countRows(); i++)
		for (int j = 0; j + piece_mask.countColumns() - 1 < fabric_mask.countColumns(); j++)
			if (!fabric_mask.overlap(piece_mask, i, j)){
				row = i;
				column = j;
				return true;
			}
	return false;
}

//---------------------------------------------------------------------------------------------
void Fabric::placePiece(Piece &piece, Mask mask, int rotations, bool vertical_mirror, bool horizontal_mirror, int row, int column)
{
	int x = 0, y = 0;
	switch (rotations){
	case 0: {
		if (vertical_mirror) x = 1;
		else x = 0;
		if (horizontal_mirror) y = 1;
		else y = 0;
	} break;
	case 1: {
		if (vertical_mirror) x = 0;
		else x = 1;
		if (horizontal_mirror) y = 1;
		else y = 0;
	} break;
	case 2: {
		if (vertical_mirror) x = 0;
		else x = 1;
		if (horizontal_mirror) y = 0;
		else y = 1;
	} break;
	case 3: {
		if (vertical_mirror) x = 1;
		else x = 0;
		if (horizontal_mirror) y = 0;
		else y = 1;
	} break;
	}
	piece.translateMe(QPointF(column * this->resolution + x * (mask.width() - piece.width()), row * this->resolution + y * (mask.height() - piece.height())));
}

//-------------------------------------------------------------------------------------------
Fabric::~Fabric()
{}

//-------------------------------------------------------------------------------------------
